package _interview100;

import _object.ListNode;

import java.util.HashSet;

/**
 * 160. 相交链表
 */
public class No160 {
    /**
     * 1.暴力
     */
    public ListNode getIntersectionNode1(ListNode headA, ListNode headB) {
        ListNode sentB = new ListNode(-1);
        sentB.next = headB;
        while (headA != null) {
            while (headB != null) {
                if (headA == headB) {
                    return headA;
                }
                headB = headB.next;
            }
            headB = sentB.next;
            headA = headA.next;
        }
        return null;
    }

    /**
     * 2.哈希表
     */
    public ListNode getIntersectionNode2(ListNode headA, ListNode headB) {
        HashSet<ListNode> hashSet = new HashSet<>();
        while (headA != null) {
            hashSet.add(headA);
            headA = headA.next;
        }
        while (headB != null) {
            if (hashSet.contains(headB)) {
                return headB;
            }
            headB = headB.next;
        }
        return null;
    }

    /**
     * 3.双指针
     */
    public ListNode getIntersectionNode3(ListNode headA, ListNode headB) {
        ListNode sentA = new ListNode(-1), sentB = new ListNode(-1);
        sentA.next = headA;
        sentB.next = headB;
        while (true) {
            if (headA == headB) return headA;
            else if (headA == null) headA = sentB.next;
            else if (headB == null) headB = sentA.next;
            else {
                headA = headA.next;
                headB = headB.next;
            }
        }
    }
}
